package com.salim.leetcode.$148;

public class SortList {
    //分治法
    //第一步 先找到链表中点 使用$876 MiddleOfTheLinkedList 分割成左右两个链表
    //第二步 递归直到只剩2个 排序
    //第三步 返回递归结果 使用$21 MergeTwoSortedLists 合并两个排好序的链表 最后返回头
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode middle = loop(middleNodeAndClearPrev(head));
        head = loop(head);
        return mergeTwoLists(head,middle);
    }

    public ListNode loop(ListNode head){
        if(head==null||head.next==null){
            return head;
        }
        if(head.next.next==null){
            if(head.val<head.next.val){
                return head;
            }else{
                ListNode result = head.next;
                result.next = head;
                result.next.next = null;
                return result;
            }
        }
        ListNode middle = loop(middleNodeAndClearPrev(head));
        head = loop(head);
        return mergeTwoLists(head,middle);
    }


    public ListNode mergeTwoLists(ListNode l1, ListNode l2){
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else{
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    public ListNode middleNodeAndClearPrev(ListNode head) {
        ListNode slow = new ListNode();
        ListNode fast = new ListNode();
        slow.next = head;
        fast.next = head;
        ListNode prevSlow = slow;
        while (fast.next!=null){
            prevSlow = slow;
            slow = slow.next;
            fast = fast.next;
            if(fast.next!=null){
                fast = fast.next;
            }else{
                prevSlow.next = null;
                return slow;
            }
        }
        slow = slow.next;
        //这里多了一步断链的操作
        if(prevSlow.next!=null){
            prevSlow = prevSlow.next;
            prevSlow.next = null;
        }
        return slow;
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
